class Solution {
public:
    string longestPalindrome(string s) {
        int res = 0;
        int res_begin = 0;
        for(int i = 0; i < s.size(); i++)
        {
            int left = i - 1;
            int right = i + 1;

            int cnt_begin = i;
            int cnt_end = i;
            while(right < s.size())
            {
                if(s[i] == s[right])
                {
                    i++;
                    cnt_end = right++;
                }
                else   
                    break;
            }
            while(left>=0 && right<s.size())
            {
                if(s[left] == s[right])
                {
                    cnt_begin = left--;
                    cnt_end = right++;
                }
                else
                    break;
            }

            if(res < cnt_end-cnt_begin+1)
            {
                res = cnt_end-cnt_begin+1;
                res_begin = cnt_begin;
            }
        }

        return s.substr(res_begin ,res);
    }
};

// dp
class Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty()) return "";
        std::vector<std::vector<int>> dp(s.size(), std::vector<int>(s.size()));
        for(int i = 0; i < s.size(); i++)
            dp[i][i] = 1;

        int res_len = 1;
        int res_begin = 0;

        for(int len = 2; len <= s.size(); len++)
        {
            for(int left = 0; left < s.size(); left++)
            {
                int right = len + left - 1;
                if(right >= s.size())
                    break;
                if(s[left] != s[right])
                    dp[left][right] = 0;
                else
                {
                    if(right-left+1 < 3)
                        dp[left][right] = 1;
                    else
                        dp[left][right] = dp[left+1][right-1];
                }

                if(dp[left][right] && res_len < right-left+1)
                {
                    res_len = right-left+1;
                    res_begin = left;
                }
            }
        }

        return s.substr(res_begin, res_len);
    }
};